//
// Description: 206. 反转链表
// Created by Loading on 2021/9/9.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>

using namespace std;

/* 迭代 */
ListNode *reverseList(ListNode *head) {
    ListNode *res = nullptr;
    ListNode *curr = head;
    while (curr) {
        ListNode *ne = curr->next;
        curr->next = res;
        res = curr;
        curr = ne;
    }

    return res;
}

/* 递归 */
ListNode *reverseList_Recursion(ListNode *head) {
    if (!head || !head->next) {
        return head;
    }
    ListNode *res = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;

    return res;
}

int main() {
    auto *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

    // 迭代
    auto res = reverseList(head);
    auto temp = res;
    while (res) {
        cout << res->val << " ";
        res = res->next;
    }
    cout << endl;

    // 递归
    res = reverseList_Recursion(temp);
    while (res) {
        cout << res->val << " ";
        res = res->next;
    }
    cout << endl;

    return 0;
}